package leetcode_acm.array;

import javax.swing.*;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月20日 21:42
 */
public class ReorderList {
    private class ListNode{
        int val;
        ListNode next;
    }
    public void reorderList(ListNode head) {
        if(head == null || head.next == null){
            return;
        }
        ListNode slow = head,fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //1->2->3->4
        slow.next= null;
        //找到中点之后,将[slow,fast]之间的给翻转,这里使用迭代法
        ListNode pre = null,cur = slow;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //此时pre就是翻转之后的头部,然后执行一个归并
        ListNode l = head,r = pre;
        while (r != null){
            ListNode lTemp = l.next;
            ListNode rTemp = r.next;
            l.next = r;
            l = lTemp;
            r.next = l;
            r = rTemp;
        }
    }
}
